package com.itheima.leetcode.od.b.dynamicprogramming;

/**
 * (C卷,100分)- 字符串序列判定（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * 输入两个字符串 S 和 L ，都只包含英文小写字母。S长度 ≤ 100，L长度 ≤ 500,000。判定S是否是L的有效子串。
 * <p>
 * 判定规则：S 中的每个字符在 L 中都能找到（可以不连续），且 S 在Ｌ中字符的前后顺序与 S 中顺序要保持一致。（例如，S = ”ace” 是 L= ”abcde” 的一个子序列且有效字符是a、c、e，而”aec”不是有效子序列，且有效字符只有a、e）
 * <p>
 * 输入描述
 * <p>
 * 输入两个字符串 S 和 L，都只包含英文小写字母。S长度 ≤ 100，L长度 ≤ 500,000。
 * <p>
 * 先输入S，再输入L，每个字符串占一行。
 * <p>
 * 输出描述
 * <p>
 * S 串最后一个有效字符在 L 中的位置。（首位从0开始计算，无有效字符返回-1）
 * <p>
 * 用例
 * <p>
 * 输入
 * ace
 * abcde
 * 输出	4
 * 说明	无
 * <p>
 * 输入
 * fgh
 * abcde
 * 输出	-1
 * 说明	无
 */
public class FirstLCSubsequence {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        String s = sc.nextLine();
        String source = sc.nextLine();*/

        String target = "ace";
        String source = "abcde";
//        System.out.println(getResult(s, source));
        System.out.println(getResult2(target, source));
    }

    /**
     * 双指针
     *
     * @param target
     * @param source
     * @return
     */
    public static int getResult(String target, String source) {
        int i = 0;
        int j = 0;

        while (i < target.length() && j < source.length()) {
            if (target.charAt(i) == source.charAt(j)) {
                i++;
            }
            j++;
        }

        if (i == target.length()) {
            return j - 1;
        } else {
            return -1;
        }
    }

    /**
     * 动态规划
     *
     * @param target
     * @param source
     * @return
     */
    public static int getResult2(String target, String source) {
        int m = target.length();
        int n = source.length();

        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (target.charAt(i - 1) == source.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Integer.max(dp[i - 1][j], dp[i][j - 1]);
                }

                if (m == dp[i][j]) {
                    return j - 1;
                }
            }
        }

        return -1;
    }
}
